package DynamicProgramming;

/**
 * @author: Darven
 * @createTime: 2025-08-02  14:33
 * @description: 5. 最长回文子串
 * - 题目：给你一个字符串 s，找到 s 中最长的 回文 子串。
 * - 题解
 *      - 1.回文字符串特点：从前往后，从后往前一致
 *      - 2.如果一个字符串是回文的，去掉首位，依然还是回文的，所以可以退出 dp[i][j]=dp[i+1][j-1]
 *      - 3.单个字符串是回文的 dp[i][i]
 *      - 4.如果是len<3，也就是len=2，前后相等，这个是回文的
 *      - 5.找到长度  j-i+1是字符串长度 使用begin记录开始位置，maxn计算出长度
 *      - 6.使用字符串切割找到最长回文字符串
 */
public class P5 {
    public static void main(String[] args) {
        P5Demo p5Demo = new P5Demo();
        System.out.println(p5Demo.longestPalindrome("babad"));
    }
}

class P5Demo {
    public String longestPalindrome(String s) {
        // 获取长度
        int l = s.length();

        if (l < 2) {
            return s;
        }

        // 转化成字符数组
        char[] array = s.toCharArray();
        // 定义最大长度
        int maxn = 1;
        // 定义开始位置
        int begin = 0;

        // 定义dp数组，dp[i][j]表示i-j长度的数组，使用boolean
        boolean[][] dp = new boolean[l][l];

        for (int i = 0; i < l; i++) {
            // 单个字母就是回文
            dp[i][i] = true;
        }

        // 从初始长度2开始遍历
        for (int L = 2; L <= l; L++) {
            // 进行每个长度的遍历
            for (int i = 0; i < l; i++) {
                // 计算j  j-i+1=L => j=L+i-1
                int j = L + i - 1;

                if (j >= l) {
                    break;
                }

                // 判断
                if (array[i] != array[j]) {
                    dp[i][j] = false;
                } else {
                    // 如果子字符串是回文，那么该字符串就是回文的
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 如果是最长回文字符串，就纪录
                if (dp[i][j] && j + i - 1 > maxn) {
                    maxn = j - i + 1;
                    begin = i;
                }
            }
        }

        return s.substring(begin, begin + maxn);
    }
}
